
#include "GASelector.h"

/* ----------------------------------------------------------------------------
RouletteWheelSelector
---------------------------------------------------------------------------- */
// This selection routine is straight out of Goldberg's Genetic Algorithms 
// book (with the added restriction of not allowing zero scores - Goldberg
// does not address this degenerate case).  We look through the members of the
// population using a weighted roulette wheel.  Likliehood of selection is
// proportionate to the fitness score.
//   This is a binary search method (using cached partial sums).  It assumes 
// that the genomes are in order from best (0th) to worst (n-1).

GAGenome& GARouletteWheelSelector::select() 
{
  float cutoff;
  int i, upper, lower;

  cutoff = randObj->GARandomFloat();
	// perform a binary search
  lower = 0; upper = pop->size()-1;
  while(upper >= lower){
    i = lower + (upper-lower)/2;
    if (!(i >= 0 && i < pop->size()))
	{
	 cerr << "lower = " << lower << ", upper = " << upper << endl;
	}
    assert(i >= 0 && i < pop->size());
    if(psum[i] > cutoff)
      upper = i-1;
    else
      lower = i+1;
  }
 
  if (lower >= pop->size())
	lower = pop->size() -1;
  return pop->individual(lower);
}


void GARouletteWheelSelector::update(const GAPopulation *rpop) 
{
  int n = rpop->size();
  this->pop = rpop;

  if(psum == NULL || pop->size() != n)
	{
	if (psum)
    	    delete [] psum;
    	n = pop->size();
    	psum = new float [n];
  	}

   if(pop->fitmax() == pop->fitmin())
	{
        for(int i=0; i<n; i++)
 	  psum[i] = (float)(i+1)/(float)n;	// equal likelihoods
    	}
   else if((pop->fitmax() > 0 && pop->fitmin() >= 0) ||
	    (pop->fitmax() <= 0 && pop->fitmin() < 0))
	{
	psum[0] = pop->individual(0).evaluate();
	for(int i=1; i<n; i++)
	  psum[i] = pop->individual(i).evaluate() + psum[i-1];
	for(int i=0; i<n; i++)
	  psum[i] /= psum[n-1];
        }
}

/* ----------------------------------------------------------------------------
TournamentSelector

  Pick two individuals from the population using the RouletteWheel selection
method.  Then return the better of the two individuals.  This is derived from
the roulette wheel selector so that we can use its update method.
---------------------------------------------------------------------------- */
GAGenome& GATournamentSelector::select() 
{
  GAGenome& genome0 = GARouletteWheelSelector::select();
  GAGenome& genome1 = GARouletteWheelSelector::select();

  float fit0 = genome0.evaluate();
  float fit1 = genome1.evaluate();

  return (fit0 > fit1) ? genome0 : genome1;
}

